BOJ_1976_여행가자

그래프 탐색 문제로 볼 수 있지만 탐색이 아니라 그래프 정점 간의 관계를 알아내는 문제
그래프 알고리즘으로 풀 수는 있지만 문제 의도에 맞게 풀려면 서로소 집합으로 푸는 것이 적절하다

도시를 중복 방문해도 괜찮고, 여행 경로 중간에 다른 도시를 탐색해도 괜찮다
-> A라는 도시와 B라는 도시가 연결되어 있는지만 확인하면 된다

1~N까지 숫자의 최상위 노드를 저장할 수 있는 parents 배열을 만들고
m, n 의 노드가 연결되어 있다면 두 노드를 union 해준다
이러한 과정을 거쳐 마지막에 입력 받는 여행루트가 모두 같은 번호의 최상위 노드를 갖는다면 여행지는 연결되어 있는 것이고, 그렇지 않다면 여행지는 연결되어 있지 않다

package BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class BJO_1976_여행가자 {  
  
    static int[] parents;  
  
    public static void main(String[] args) throws IOException {  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       StringTokenizer st;  
       int N = Integer.parseInt(br.readLine());  
       int M = Integer.parseInt(br.readLine());  
  
       parents = new int[N + 1];  
       // 배열 초기화  
       for (int i = 1; i <= N; i++) {  
          makeset(i);  
       }  
  
       for (int i = 1; i <= N; i++) {  
          st = new StringTokenizer(br.readLine());  
          for (int j = 1; j <= N; j++) {  
             if (Integer.parseInt(st.nextToken()) == 1) {  
                // 연결되어 있다면 유니온 한다  
                union(i, j);  
             }  
          }  
       }  
  
       st = new StringTokenizer(br.readLine());  
       // 시작하는 노드  
       int root = findset(Integer.parseInt(st.nextToken()));  
       while (st.hasMoreTokens()) {  
          int num = Integer.parseInt(st.nextToken());  
          // 만약 연결되어 있지 않다면??  
          if (root != findset(num)) {  
             System.out.println("NO");  
             return;  
          }  
       }  
       System.out.println("YES");  
    }  
  
    static void makeset(int x) {  
       parents[x] = x;  
    }  
  
    static int findset(int x) {  
       if (x == parents[x]) {  
          return x;  
       }  
  
       return parents[x] = findset(parents[x]);  
    }  
  
    static void union(int x, int y) {  
       parents[findset(x)] = findset(y);  
    }  
}

#서로소집합